package com.skh.string;

import java.util.Stack;

/**
 * @Author skh
 * @Date 2020/3/27 10:59
 * @Desc 分割平衡字符串
 */
public class BalancedStringSplit {

    /**
     * 在一个「平衡字符串」中，'L' 和 'R' 字符的数量是相同的。
     *
     * 给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
     *
     * 返回可以通过分割得到的平衡字符串的最大数量。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：s = "RLRRLLRLRL"
     * 输出：4
     * 解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。
     * 示例 2：
     *
     * 输入：s = "RLLLLRRRLR"
     * 输出：3
     * 解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。
     * 示例 3：
     *
     * 输入：s = "LLLLRRRR"
     * 输出：1
     * 解释：s 只能保持原样 "LLLLRRRR".
     */


    /*
    方法一:数组模拟栈
    核心算法是通过取容器顶部的字母来甄别是否与未来要放入容器的字母是互异的。

    每次遇到不一样的，我们把当前字母擦除掉（通过指针位置移动就行）
    遇到一样的，就堆积在容器中。
    但每次擦除完，都检查容器的 size 是否等于 0，是则表明堆积的都被消灭了，找到了一个平衡字符串，计数器加 1。

     */
    public int balancedStringSplit(String s) {
        Stack<Character> stack = new Stack<>();
        int count = 0;
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (stack.size() == 0 || c == stack.peek()) {
                stack.push(c);
            } else if (c != stack.peek()) {
                stack.pop();
                if (stack.size() == 0) {
                    count++;
                }
            }
        }

        return count;
    }

    /*
    首先以 R 为基准，设立一个 专门记录 R 的数量的计数器 counter_R。

    遍历字符串 s，是 'R' 计数器 couter_R 加 1，
    遇到 'L' 则认为是消灭 R 的，counter_R 自减 1
    每次消灭 R，都遍历完一次，检查在这之前的 R 是否还有剩余
    没有剩余的话，该位置之前的算是一个由相同数量 L 与 R 组成的 「平衡字符串」。

     */
    public int balancedStringSplit1(String s) {
        int count = 0;
        int countR = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == 'R') {
                countR++;
            } else {
                countR--;
            }

            if (countR == 0) {
                count++;
            }
        }

        return count;
    }
}
